#include "project4.h"
#include <vector>
#include <list>
#include <fstream>
#include <time.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
//
void convertPackages(Package * packages, int * weight, int * values, int size)
{
	for (int i = 0; i < size; i++)
	{
		weight[i] = packages[i].Weight;
		values[i] = packages[i].Value;
	}
}

list<int> DynamicKnapsack(int * weight, int * values, int numOfPackages, int maximumWeight)
{
    list<int> **m = 0;
    // create the rows
    // there are a total of n rows
    m = new list<int>*[numOfPackages];
    // create the columns
    // the columns are allocated from the rows
    for (int i = 0; i < numOfPackages; i++)
    {
        m[i] = new list<int>[maximumWeight];
    }

    // make the first column empty
    // not needed, as the list is implicitly empty
    // make the first row empty
    // not needed as the list is implicitly empty
    
	list<int> dont_include;
	list<int> do_include;
	for (int i = 1; i < numOfPackages; i++)
	{
		for (int j = 1; j < maximumWeight; j++)
		{
			if (weight[i - 1] > j)
			{
				m[i][j] = m[i - 1][j];
			}
			else
			{
                do_include.clear();
                dont_include.clear();
				dont_include = m[i - 1][j];
                do_include = m[i - 1][j - weight[i - 1]];
                do_include.push_back(i - 1);
                if  (   total_votes(do_include, values, numOfPackages)  > 
                        total_votes(dont_include, values, numOfPackages)
                    )
                {
                    m[i][j] = do_include;
                } 
                else
                {
                    m[i][j] = dont_include;
                }
			}
		}
	}
    list<int> best = m[numOfPackages - 1][ maximumWeight - 1];
    for (int i = 0; i < numOfPackages; i++)
    {
        delete [] m[i];
    }
    delete [] m;

    return best;
}

int total_votes( list<int> data, int * values, int maxNumOfValues )
{
    int total = 0;
    for (list<int>::iterator it = data.begin(); it != data.end(); it++)
    {
        total += values[*it];
    }
    return total;
}

SET CreateSet( Package * packages, list<int> indices )
{
    SET newSet;
    for (list<int>::iterator it = indices.begin(); it != indices.end(); it++)
    {
        newSet.push_back(&packages[*it]);
    }
    return newSet;
}


void MediaTests()
{    
    MediaTest(720);
    MediaTest(1440);
    MediaTest(25600);
    MediaTest(65536);
    MediaTest(716800);
}

void MediaTest( int w )
{     
    Package * packages = getPackages("packages.txt", 200);
    int n = 200;    
    int * weight = new int[200];
    int * values = new int[200];
    list<int> knapResult;
    SET knapSet;

    knapResult.empty();
    knapSet.empty();
    convertPackages(packages, weight, values, 20);
    long testResult = clock();
    knapResult = DynamicKnapsack(weight, values, 20, 1000);
    testResult = clock()- testResult;
    knapSet = CreateSet(packages, knapResult);
    cout << "N = 200 " << "W = " << w << endl;
    PrintSet(knapSet);
    cout << "Run-time: " << testResult << endl << endl;

    delete weight;
    delete values;
    delete packages;
}

void nthousand()
{
    int n = 1000;
    int w = 720;
    Package * packages = getPackages("packages.txt", n);    
    int * weight = new int[n];
    int * values = new int[n];
    list<int> knapResult;
    list<int> lastResult;
    long testResult = 0;

    convertPackages(packages, weight, values, n);
    while (testResult <= 600000)
    {               
        cout << endl << "Dynamic Knapsack: " << endl << "n = " << n << "w = " << w << endl;
        lastResult = knapResult;
        testResult = clock();
        knapResult = DynamicKnapsack(weight, values, n, w);
        testResult = clock() - testResult;
        w += 100; 
        cout << "Run-time: " << testResult << endl;
    }
    w -= 100;
    cout << "Max weight with n = 1000 is: " << w << endl;
    SET knapSet = CreateSet(packages, lastResult);
    PrintSet(knapSet);
    delete packages;
    delete weight;
    delete values;
}